#include <iostream>
#include <stdlib.h>
#include <memory>
#include "very_long.h"

Long::Long()
{
	n = 0;
}
Long::Long(int c)
{
	if (c / Osn)
	{
		n = 2;
		a[0] = c % Osn;
		a[1] = c / Osn;
	}
	else
	{
		n = 1;
		a[0] = c;
	}
}

Long::~Long(){}

istream& operator >>(istream& is, Long& l)
{
	int i;
	char c;
	do
		is.get(c);
	while (c < '0' || c > '9');

	l.n = 1;
	memset(l.a, 0, NMax);
	while (c >= '0' && c <= '9')
	{
	    for(i = l.n - 1; i >= 0; i--)
		{
			l.a[i + 1] += int(l.a[i] * 10) / Osn;
			l.a[i] = int(l.a[i] * 10) % Osn;
		}
		l.a[0] += int(c - '0');
	    if (l.a[l.n] > 0) 
			l.n++;
		is.get(c);
	}
	return is;
}

ostream& operator <<(ostream& os, Long& l)	
{
	int i, j, ls = Osn;
	char s[20];
	
	_itoa_s(ls, s, 10);
	ls = int(strlen(s));
	ls--;
		
	os << l.a[l.n - 1];
	for(i = l.n - 2; i >= 0; i--)
	{
		_itoa_s(l.a[i], s, 10);
		for(j = int(strlen(s)); j < ls; j++)
			os << '0';
		os << l.a[i];
	}
	os << '\n';
	return os;
}

bool operator ==(const Long& l1, const Long& l2)
{
	if (l1.n != l2.n)
		return false;
	else
	{
		for(int i = 0; i < l1.n; i++)
			if (l1.a[i] != l2.a[i])
				return false;
	}
	return true;
}

bool operator > (const Long& l1, const Long& l2)
{

	if (l1.n < l2.n)
		return false;
	else
	    if (l1.n > l2.n)
			return true;
		else
		{
			int i = l1.n;
			while (i > 0 && l1.a[i] == l2.a[i])
				i--;
			if (i == 0)
				return false;
			else
				if (l1.a[i] > l2.a[i])
					return true;
				else
					return false;
		}
}

bool operator < (const Long& l1, const Long& l2)
{

	if (l1.n > l2.n)
		return false;
	else
	    if (l1.n < l2.n)
			return true;
		else
		{
			int i = l1.n;
			while (i > 0 && l1.a[i] == l2.a[i])
				i--;
			if (i == 0)
				return false;
			else
				if (l1.a[i] < l2.a[i])
					return true;
				else
					return false;
		}
}

Long operator + (const Long& l1, const Long& l2)
{
	Long c;
	memset(c.a, 0, NMax);
	int i, k;

	if (l1.n > l2.n)
		k = l1.n;
	else
		k = l2.n;
	for(i = 0; i < k; i++)
	{
		c.a[i + 1] = (c.a[i] + l1.a[i] + l2.a[i]) / Osn;
		c.a[i] = (c.a[i] + l1.a[i] + l2.a[i]) % Osn;
	}
	if (c.a[k] == 0)
		c.n = k;
	else
	    c.n = k + 1;
	return c;
}

Long operator - (const Long& l1, const Long& l2)
{
	Long c = l1;
	int i, j;
	for(i = 0; i < l2.n; i++)
	{
		c.a[i] -= l2.a[i];
		j = i;
		while (c.a[j] < 0 && j <= c.n)
		{
			c.a[j] += Osn;
			c.a[j + 1]--;
			j++;
		}
	}
	i = c.n - 1;
	while (i > 1 && c.a[i] == 0)
		i--;
	c.n = i + 1;
	return c;
}

Long operator * (const Long& l1, const Long& l2)
{
	int i, j, dv;
	Long c;
	memset(c.a, 0, NMax);
	for(i = 0; i < l1.n; i++)
		for(j = 0; j < l2.n; j++)
		{
			dv = l1.a[i] * l2.a[j] + c.a[i + j];
			c.a[i + j + 1] += dv / Osn;
			c.a[i + j] = dv % Osn;
		}
	c.n = l1.n + l2.n;
	while (c.n > 1 && c.a[c.n - 1] == 0) 
		c.n--;
	return c;
}



Long operator * (const Long& l, const int& k)
{
  	Long c;
	memset(c.a, 0, NMax);
	if (k == 0)
		c.n = 1;
	else
	{
		int i;
		for(i = 0; i < l.n; i++)
		{
			c.a[i + 1] = (l.a[i] * k + c.a[i]) / Osn;
			c.a[i]     = (l.a[i] * k + c.a[i]) % Osn;
		}
		if (c.a[l.n] > 0)
			c.n = l.n + 1;
		else
			c.n = l.n;
	}
	return c;
}

Long operator * (const int& k, const Long& l)
{
  	Long c;
	memset(c.a, 0, NMax);
	if (k == 0)
		c.n = 1;
	else
	{
		int i;
		for(i = 0; i < l.n; i++)
		{
			c.a[i + 1] = (l.a[i] * k + c.a[i]) / Osn;
			c.a[i]     = (l.a[i] * k + c.a[i]) % Osn;
		}
		if (c.a[l.n] > 0)
			c.n = l.n + 1;
		else
			c.n = l.n;
	}
	return c;
}

Long pow(Long& l, int p)
{
	Long c(1);
	for(int i = 0; i < p; i++)
		c = c * l;
	return c;
}
